The present invention relates generally to object-based high level programming environments, and more particularly, to techniques for tracking references to objects defined in object-based high level programming environments.
Recently, the Java programming environment has become quite popular. The Java programming language is a language that is designed to be portable enough to be executed on a wide range of computers ranging from small devices (e.g., pagers, cell phones and smart cards) up to supercomputers. Computer programs written in the Java programming language (and other languages) may be compiled into Java Bytecode instructions that are suitable for execution by a Java virtual machine implementation.
The Java virtual machine is commonly implemented in software by means of an interpreter for the Java virtual machine instruction set but, in general, may be software, hardware, or both. A particular Java virtual machine implementation and corresponding support libraries together constitute a Java runtime environment.
Computer programs in the Java programming language are arranged in one or more classes or interfaces (referred to herein jointly as classes or class files). Such programs are generally platform, i.e., hardware and operating system, independent. As such, these computer programs may be executed without modification on any computer that is able to run an implementation of the Java runtime environment.
Object-oriented classes written in the Java programming language are compiled to a particular binary format called the xe2x80x9cclass file format.xe2x80x9d The class file includes various components associated with a single class. These components can be, for example, methods and/or interfaces associated with the class. In addition, the class file format can include a significant amount of ancillary information that is associated with the class. The class file format (as well as the general operation of the Java virtual machine) is described in some detail in The lava Virtual Machine Specification, Second Edition, by Tim Lindholm and Frank Yellin, which is hereby incorporated herein by reference.
As an object-oriented programming language, Java utilizes the programming concept known as an object. In the Java programming environment, Java objects are created (instantiated) from Java classes. Typically, Java objects are stored in a heap memory portion (heap). To illustrate, FIG. 1 depicts a computing environment 100 including a heap memory portion 102 suitable for storing Java objects. As shown in FIG. 1, various Java objects, for example, objects O1, O2, O3, O4, O5 and O6 can be stored in the heap memory portion 102. A Java object in the memory portion 102, for example, Java object O3, can include a reference to its class, as well as one or more other fields describing data (e.g., variables) associated with the object. The Java object O3 can also include references to other Java objects, for example, Java objects O4 and O5, which are also stored in the heap memory portion 102.
Java objects are typically created in the heap memory portion 102 when they are instantiated. After a Java object has been instantiated, it can be referenced from various points in the Java program. For example, the object O3 can be referenced by a local variable 104 of the Java program. During the execution time of the Java program, as depicted in FIG. 1, the local variable 104 can be on an execution stack 106 in a stack frame portion 108. The stack frame portion 108 represents the stack frame for a method associated with the local variable 104. The stack frame portion 108 is typically placed on the execution stack 106 when the associated method is invoked.
In addition to the local variables associated with the method, the stack frame portion 108 also includes an operand stack portion 110 suitable for placing various operands on the execution stack 106. In the Java programming environment, these operands are placed on the operand stack portion 110 of the execution stack 106 in order to execute the Java method associated with the stack frame 108. As is known to those skilled in the art, these operands can be references to objects stored in the heap memory portion 102, e.g., an operand 112 referencing the Java object O3.
As is known to those skilled in the art, there may be a need to identify and track references to Java objects for various reasons. For example, during the course of the execution of Java programs, some of the objects in the heap memory portion 102 are no longer needed (i.e., become xe2x80x9cdead objectsxe2x80x9d which are no longer reachable by the Java program). Accordingly, it is desirable to identify the xe2x80x9cdeadxe2x80x9d objects in the heap memory portion 102 and remove them from the heap. This operation can be referred to as xe2x80x9cgarbage collection.xe2x80x9d
As noted above, entries of the execution stack can be references to Java objects stored in the heap memory portion. Therefore, to perform garbage collection for Java programs, there is a need to identify entries on the execution stack that are references to objects stored on the heap memory portion. The conservative approach to garbage collection would require traversing the execution stack and identifying every entry on the stack that could potentially be a reference to an object in the heap. Unfortunately, this conservative approach typically results in identifying dead objects as live objects. Since an object in the heap may refer to other objects, identifying a dead object as a live one can seriously hinder garbage collection.
Another approach to garbage collection seeks to identify references to live objects more accurately. However, this approach requires use of another interpreter, namely, the abstract interpreter. The abstract interpreter essentially simulates the execution of Java methods and operates when the main interpreter is suspended. Thus, the use of an abstract interpreter can adversely effect performance of Java programs. Moreover, devoting memory space and execution time to use an interpreter is not a feasible method for computing systems with relatively limited resources (e.g., embedded systems with relatively smaller memory and computing power).
In view of the foregoing, there is a need for improved techniques for tracking and identifying references to Java objects.
Broadly speaking, the present invention relates to improved techniques for identifying and tracking references to Java objects. As will be appreciated, the techniques can be used in a variety of applications. For example, the techniques can be used to implement garbage collection methods for Java programs in a manner that is more efficient, especially for systems with limited resources (e.g., embedded systems). In accordance with one aspect of the invention, a reference stack suitable for storing references to Java objects is disclosed. In one embodiment, for each execution stack, a reference stack is designated. In fact, the reference stack can be used to store references to Java objects in the same offset as they appear in the corresponding execution stack.
In accordance with another aspect of the invention, references to Java objects can be identified based on the values stored in the reference stack. In one embodiment, the reference stack is traversed to identify the entries that correspond to active Java objects. These entries are then checked against the corresponding entries in the execution stack to ensure with a greater degree of certainty that the identified entries represent references to active Java objects.
The invention can be implemented in numerous ways, including as a method, an apparatus, a computer readable medium, and a database system. Several embodiments of the invention are discussed below.
As a method of tracking references to objects of an object-oriented programming language, one embodiment of the invention includes the acts of: providing a reference stack associated with an execution stack; determining whether at least one value should be stored in the reference stack; and storing said at least one value in the reference stack when the determining determines that the at least one object should be stored in the reference stack.
As a method of tracking references to Java objects, another embodiment of the invention includes the acts of: providing a reference stack associated with an execution stack, the reference stack being the same size as the execution stack; determining whether at least one value should be stored in the reference stack, wherein the determining is performed during Bytecode verification; and storing the at least one value in the reference stack in an offset that is the same as the offset in the execution stack where the value is stored when the determining determines that the at least one object should be stored in the reference stack.
One embodiment of the invention provides a reference stack suitable for storing references to objects of a computer program written in an object-oriented programming language. The reference stack corresponds to an execution stack of the computer program which is also suitable for storing references to objects of the computer program. In addition, at least one reference to an object is stored both on the reference stack and the execution stack.
As a method for identifying references to Java objects, one embodiment of the invention includes the acts of: reading a value stored in an entry of a reference stack; determining whether the value is equal to another value that is stored in a corresponding entry of an execution stack; and marking the value in the entry of the reference stack as a reference to a Java object when the determining determines that the value is equal to the another value stored in the corresponding entry of the execution stack.
These and other aspects and advantages of the present invention will become more apparent when the detailed description below is read in conjunction with the accompanying drawings.